Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра ЕОМ / Звіт з лабораторної роботи № 2 з дисципліни: «Алгоритми та методи обчислень» на тему: “Асимптотичні характеристики складності алгоритму. Алгоритми з поліноміальною та експоненціальною складністю”  Мета роботи: ознайомитись з асимптотичними характеристиками складності та класами складності алгоритмів. Теоретична частина В процесі розв’язку задачі вибір алгоритму викликає певні труднощі. Алгоритм повинен задовільняти вимогам, які часом суперечать одна одній: = бути простим для розуміння, переводу в програмний код, відлягодження. = ефективно використовцвати комп'ютерні ресурси і виконуватись швидко. Якщо програма повинна виконуватись декілька разів, то перша вимога більш важлива. Вартість робочого часу програміста перевищує вартість машинного часу виконання програми, тому вартість програми оптимізується по вартості написання ( а не виконання) програми. Якщо задача вимагає значних обчислювальних витрат, то вартість виконання програми може перевищити вартість написання програми, особливо коли програма повинна виконуватись багаторазово. Але навіть в цій ситуації доцільно спочатку реалізувати простий алгоритм, і з'ясувати яким чином повинна себе поводити більш складна програма. На час виконання програми впливають наступні чинники: = ввід інформації в програму = якість скомпільованого коду = машинні інструкції, які використовуються для виконання програми = часова складність алгоритму (ЧС) Часова складність є функцією від вхідних даних. Для деяких задач ЧС залежить від самих вхідних даних (знаходження найбільшого спільного дільника двох чисел), для інших – від їх "розміру" (задачі сортування). Коли ЧС є функцією від самих даних, її визначають як ЧС для найгіршого випадку, тобто як найбільшу кількість інструкцій програми серед всіх можливих вхідних даних для цього алгоритму. Використовується також ЧС в середньому ( в статистичному сенсі ), як середня кількість інструкцій по всім можливим вхідним даним. На практиці ЧС в середньому важче визначити ніж ЧС для найгіршого випадку, черезте що це математично важка для розв'язання задача, та, крім того, іноді важко визначити, що означає "середні" вхідні дані. Коли ЧС є функцією від кількості вхідних даних, аналізується швидкість зростання цієї функції. Асимптотичні співвідношення Для опису швидкості зростання функцій використовується О-символіка. Функція f(n) має порядок зростання O(g(n)), якщо що існують додатні константи С i n0 такі, що f(n) <= С*g(n), для n > n0. Позначемо функцію яка виражає залежність часової складності від кількості вхідних даних (n) через L(n) Тоді, наприклад, коли говорять, що часова складність L(n) алгоритму має порядок(степінь) зростання O(n2) (читається як "О велике від n в квадраті, або просто "о від n в квадраті", то вважається, що існують додатні константи c i n0 такі, що для всіх n, більших або рівних n0, виконується нерівність L(n)<=cn2. Наприклад, функція L(n) = 3n3+2n2 має порядок зростання O(n3). Нехай n0=0 і с = 5. Очевидно, що для всіх цілих n>=0 виконується нерівність 3n3+2n2 <= 5n3. Коли кажуть, що L(n) має степінь зростання O(f(n)) , то вважається, що f(n) є верхньою границею швидкості зростання L(n). Щоби вказати нижню границю швидкості зростання L(n) використовують позначення ((g(n)) , що означає існування такої константи с , що для нескінченогї кількості значень n виконується нерівність L(n)>=c g(n). На практиці визначення порядку зростання є задачею, що цілком вирішується за допомогою кількох базових принципів. Існують три правила для визначення складності: O(с* f(n))=O(f(n)) O(f(n) + g(n)) = O(max(f(n), g(n))) O(f(n) * g(n)) = O(f(n)) * O(g(n)) Перше правило декларує, що постійні множники не мають значення для визначення порядку зростання. Друге правило називається "Правило сум". Це правило використовується для послідовних програмних фрагментів з циклами та розгалуженнями. Порядок зроста...